class Solution {
public:
    string letterMap[10]={
      " ",
      " ",
      "abc",
      "def",
      "ghi",
      "jkl",
      "mno",
      "pqrs",
      "tuv",
      "wxyz",
    };
    string ans;
    vector<string> res;
    void backtrack(string digits,int index){
      if(ans.size() == digits.size()){
        res.push_back(ans);
        return;
      }
      int digit = digits[index] - '0';
      string letter = letterMap[digit];
      for(int i = 0;i < letter.size();i++){
        ans.push_back(letter[i]);
        backtrack(digits,index + 1);
        ans.pop_back();
      }
    }
    vector<string> letterCombinations(string digits) {
       // ans.clear();
        res.clear();
        if(digits.size() == 0){
          return res;
        }
        backtrack(digits,0);
        return res;
    }
};
